package 剑指offer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class 和为s的连续正数序列 {
    //使用回溯法超时
//    ArrayList<ArrayList> lists = new ArrayList<>();
//    public int[][] findContinuousSequence(int target) {
//        ArrayList<Integer> list = new ArrayList<>();
//        dfs(target,0,1,list);
//        int[][] ans = new int[lists.size()][];
//        for (int i = 0; i < lists.size(); i++) {
//            ArrayList list1 = lists.get(i);
//            int[] ints = new int[list1.size()];
//            for (int j = 0; j < list1.size(); j++) {
//                ints[j]= (int) list1.get(j);
//            }
//            ans[i]=ints;
//        }
//        return ans;
//    }
//    private void dfs(int target, int sum, int idx, ArrayList<Integer> list) {
//        if (sum==target)
//            lists.add(new ArrayList<>(list));
//        for (int i = idx; i < target; i++) {
//            if (list.size()>0 && i-list.get(list.size()-1)!=1)
//                continue;
//            list.add(i);
//            sum+=i;
//            dfs(target,sum,i+1,list);
//            sum-=i;
//            list.remove(list.size()-1);
//        }
//    }
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        for (int l=1,r=1,sum=0;r<target;r++){
            sum+=r;
            while (sum>target)
                sum-=l++;
            if (sum==target){
                int[] ints = new int[r - l + 1];
                for (int i = 0; i < r - l + 1; i++) {
                    ints[i]=l+i;
                }
                list.add(ints);
            }
        }
        int[][] res = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            res[i]=list.get(i);
        }
        return res;
    }

    @Test
    public void test(){
        int[][] ints = findContinuousSequence(9);
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[i].length; j++) {
                System.out.print(ints[i][j]+" ");
            }
            System.out.println();
        }
    }
}
